{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# usr/bin/env python3 \n",
    "\n",
    "\n",
    "\n",
    "def bubble_sort(arry):\n",
    "    # 冒泡排序，依次比较大小，交换位置\n",
    "    i,j = 0,0\n",
    "    length = len(arry)\n",
    "    for i in range(length):\n",
    "        for j in range(i+1,length):\n",
    "            if arry[j] < arry[i]:\n",
    "                arry[j], arry[i] = arry[i], arry[j]\n",
    "            else:\n",
    "                continue\n",
    "    return arry\n",
    "\n",
    "\n",
    "def selection_sort(arry):\n",
    "    # 选择排序，每次都把最小的找出放在左边\n",
    "    length = len(arry)\n",
    "    minFlag = 0\n",
    "    for i in range(0, length):\n",
    "        print(i)\n",
    "        minFlag = i\n",
    "        for j in range(i+1,length):\n",
    "            if arry[j] < arry[minFlag]:\n",
    "                minFlag = j\n",
    "        if i != minFlag:\n",
    "            arry[i], arry[minFlag] = arry[minFlag], arry[i]\n",
    "    return arry\n",
    "\n",
    "def insertion_sort(arry):\n",
    "    # 插入排序，选取一个目标数字，从右开始比较，放在最小的位置上\n",
    "    length = len(arry)\n",
    "    for i in range(1,length):\n",
    "        preIndex = i - 1\n",
    "        while preIndex > 0 and arry[preIndex+1] < arry[preIndex]:\n",
    "            arry[preIndex+1], arry[preIndex] = arry[preIndex], arry[preIndex+1]\n",
    "            preIndex -= 1\n",
    "    return arry\n",
    "\n",
    "def merge_sort_index(array,low=0,high=0):\n",
    "    # 归并排序使用数组下标\n",
    "    if low < high:\n",
    "        mid = (low+high-1)//2\n",
    "        merge_sort_index(array,low,mid)\n",
    "        merge_sort_index(array,mid+1,high)\n",
    "        merge_arry(array,low,mid,high)\n",
    "\n",
    "def merge_arry(array,low,mid,high):\n",
    "    mergeList = []\n",
    "    left = low\n",
    "    right = mid + 1\n",
    "    while left <= mid and right <= high-1:\n",
    "        if array[left] <= array[right] :\n",
    "            mergeList.append(array[left])\n",
    "            left += 1\n",
    "        else:\n",
    "            mergeList.append(array[right])\n",
    "            right += 1\n",
    "    while left <= mid:\n",
    "        mergeList.append(array[left])\n",
    "        left += 1\n",
    "    while right <= high-1:\n",
    "        mergeList.append(array[right])\n",
    "        right += 1\n",
    "    for i in range(len(mergeList)):\n",
    "        array[low+i] = mergeList[i]\n",
    "\n",
    "def merge_sort(lists):\n",
    "    # 归并排序使用数组切片\n",
    "    if len(lists) <= 1:\n",
    "        return lists\n",
    "    num = int(len(lists)/2)\n",
    "    left = merge_sort(lists[:num])\n",
    "    right = merge_sort(lists[num:])\n",
    "    return merge(left, right)\n",
    "\n",
    "\n",
    "def merge(left, right):\n",
    "    ri, le = 0, 0\n",
    "    result = []\n",
    "    while le < len(left) and ri < len(right):\n",
    "        if left[le] < right[ri]:\n",
    "            result.append(left[le])\n",
    "            le += 1\n",
    "        else:\n",
    "            result.append(right[ri])\n",
    "            ri += 1\n",
    "    result += left[le:]   # 剩下的左边的\n",
    "    result += right[ri:]  # 剩下的右边的\n",
    "    return result\n",
    "\n",
    "\n",
    "import random\n",
    "def quick_sort(array):\n",
    "    length = len(array)\n",
    "    if length <= 1:\n",
    "        return array\n",
    "    # pivot = array[length // 2]\n",
    "    pivot = array[random.randint(0,length)]\n",
    "    lesser = [element for element in array if element < pivot]\n",
    "    greater = [element for element in array if element > pivot]\n",
    "    return quick_sort(lesser) + [pivot] + quick_sort(greater)\n",
    "\n",
    "# data = list(range(10))  # 产生一个有序列表\n",
    "# random.shuffle(data)  # 调用shuffle函数打乱顺序\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import copy\n",
    "    import time\n",
    "    array = [1,4,8,7,454,23,45,564,99,80]\n",
    "    # print(\"bubble_sort: {}\".format(bubble_sort(arry)))\n",
    "    # print(\"selection_sort: {}\".format(selection_sort(arry)))\n",
    "    # rst = insertion_sort(arry)\n",
    "    # print(\"insertion_sort: {}\".format(rst))\n",
    "    # merge_sort_index(array,low=0,high=len(array))\n",
    "    # array = merge_sort(array)\n",
    "    \n",
    "    array = quick_sort(array)\n",
    "    print(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" 二分查找 \"\"\"\n",
    "\n",
    "def binary_search(listA, target):\n",
    "    left = 0\n",
    "    right = len(listA) - 1 \n",
    "    while left <= right:\n",
    "        midpoint = (left + right) // 2\n",
    "        current_item = listA[midpoint]\n",
    "        # if listA[left] == target:\n",
    "        #     return left\n",
    "        # elif listA[right] == target:\n",
    "        #     return right\n",
    "        if current_item == target:\n",
    "            return midpoint\n",
    "        else:\n",
    "            if target < current_item:\n",
    "                right = midpoint - 1\n",
    "            else:\n",
    "                left = midpoint + 1\n",
    "    return None\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    listA = [1,4,8,9,12,45,78]\n",
    "    target = 12\n",
    "    rst = binary_search(listA, target)\n",
    "    if rst:\n",
    "        print(\"OK: \",rst)\n",
    "    else:\n",
    "        print(\"Not found !\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" 快速归并排序 \"\"\"\n",
    "\n",
    "def merge_sort_fast(listA):\n",
    "    start = []\n",
    "    end = []\n",
    "    while len(listA) > 1:\n",
    "        a = min(listA)\n",
    "        b = max(listA)\n",
    "        start.append(a)\n",
    "        end.append(b)\n",
    "        listA.remove(a)\n",
    "        listA.remove(b)\n",
    "    if listA:\n",
    "        start.append(listA[0])\n",
    "    end.reverse()\n",
    "    return start + end\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    listA = [0, 5, 3, 2, 2]\n",
    "    sortedList = merge_sort_fast(listA)\n",
    "    print(sortedList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" 递归方法处理快速排序 \"\"\"\n",
    "\n",
    "def quick_sort(listA):\n",
    "    length = len(listA)\n",
    "    if length <= 1:\n",
    "        return listA\n",
    "    else:\n",
    "        pivot = listA[0]\n",
    "        # import random\n",
    "        # pivot = random.choice(listA)\n",
    "        greater = [element for element in listA[1:] if element > pivot]\n",
    "        lesser = [element for element in listA[1:] if element <= pivot]\n",
    "        return quick_sort(lesser) + [pivot] + quick_sort(greater)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    listA = [0, 5, 3, 2, 2]\n",
    "    sortedList = quick_sort(listA)\n",
    "    print(sortedList)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
